User blog:Hyp cos/Non-Classic Growth Rate
The post is a continuation of this one. A better definition of "comparable" functions There are many definitions of eventual domination. Some are listed below from tighter to looser. #\(f\ge^*g\) (f eventually dominates or is comparable to g) if \(\exists N\forall n>N(f(n)\ge g(n))\) #\(f\ge^*g\) if \(\lim\limits_{n\to\infty}\frac{g(n)}{f(n)}\le1\) #\(f\ge^*g\) if \(\exists a,b,N\forall n>N(f(n+a)+b\ge g(n))\) #\(f\ge^*g\) if \(\exists a,b,N\forall n>N(f(an+b)\ge g(n))\) And \(f\approx g\) (f is comparable to g) if \(f\ge^*g\land g\ge^*f\). So \(f\approx f\) holds for all f. Definition #1 is very strict. There are few common functions can be classified into the same comparable class. And so is Definition #2 for fast-growing functions (googological functions). As PsiCubed2 said, Definition #3 is still too strict, if we want to eliminate the effect of "base numbers" of multivariable notations. For instance, \(\lambda n.n\uparrow\uparrow n\) (using lambda abstraction to denote functions) is not comparable to \(\lambda n.2\uparrow\uparrow n\) according to Definition #3, but they are comparable according to Definition #4. However, Definition #4 is too loose to distinguish \(H_\alpha\) and \(H_{\alpha+\beta}\) where \(\beta<\omega^2\) in Hardy hierarchy. The "resolution" of Definition #4 in the HH scale is \(\omega^2\), defined as the least \(\beta\) that \(H_\alpha\) is not comparable to \(H_{\alpha+\beta}\). Definition #3 has resolution \(\omega\). A definition of "comparable" with resolution \(<\omega\) would be too strict. Here is the definition used in this post, with resolution \(\omega\) but can eliminate the effect of "base numbers": :\(f\ge^*g\) if \(\forall a>1,b>1\exists N\forall n>N(\lfloor af(\lfloor bn\rfloor)\rfloor>g(n))\) (here \(a,b\) are real numbers) By the way, this definition, #3 and #4 are very loose in the SGH scale. Growth rate (HH) addition and subtraction If the FS system fits \((\alpha+\beta)n=\alpha+(\betan)\), then \(H_{\alpha+\beta}(n)=H_\alpha(H_\beta(n))\). The composition of functions results addition of growth rates (in HH scale). Since inverse function is the inverse of composition, we can define growth rate (in HH scale) addition and subtraction as follows. A growth rate expression is built by the following rules: #An ordinal \(\alpha\) is a growth rate expression #If \(a\) is a growth rate expression, then \((-a)\) is a growth rate expression #If \(a\) and \(b\) are growth rate expressions, then \((a+b)\) is a growth rate expression Growth rate expressions work in Hardy hierarchy as follows: #For ordinal \(\alpha\), \(H_\alpha\) works as usual #\(H_{(-a)}=H_a^{-1}\) (inverse function) #\(H_{(a+b)}=H_a\circ H_b\) (composition, i.e. \(H_{(a+b)}(n)=H_a(H_b(n))\)) Function f has growth rate \(a\) if \(f\approx H_a\). Growth rate expressions have these properties: #\(((a+b)+c)=(a+(b+c))\) (so we can omit the brackets among addition) #\((-(-a))=a\) #\((-(a+b))=(-b)+(-a)\) Further, functions with costs (e.g. Goodstein function), or even functions with costs, which again have costs, which again have costs, and so forth, can get their growth rate in the form of \(\alpha_1+(-\beta_1)+\alpha_2+(-\beta_2)+\cdots+\alpha_k+(-\beta_k)\), where \(\alpha_i\) and \(\beta_i\) are ordinals (only have addition). Growth rate (HH) multiplication and division by ordinal If the FS system fits \((\alpha\beta)n=\alpha(\betan)\), then \(H_{\alpha\beta}\) can be build in the following way: #\(h_0(n)=n\) #\(h_{\gamma+1}(n)=h_\gamma(H_\alpha(n))\) #\(h_\gamma(n)=h_{\gamman}(n)\) for limit \(\gamma\) #\(H_{\alpha\beta}=h_\beta\) From now on, it is hard to find an inverse of the operation. So it is hard to define how growth rate expressions work in Hardy hierarchy. A growth rate expression is built by the following rules: #An ordinal \(\alpha\) is a growth rate expression #If \(a\) is a growth rate expression, then \((-a)\) is a growth rate expression #If \(a\) and \(b\) are growth rate expressions, then \((a+b)\) is a growth rate expression #If \(a\) is a growth rate expression, \(\alpha\) is an ordinal, then \((a\alpha)\) is a growth rate expression #If \(a\) is a growth rate expression, \(\alpha\) is an ordinal, then \((a/\alpha)\) is a growth rate expression Growth rates work as follows: #Function f has growth rate \(\alpha\) if \(f\approx H_\alpha\) #Function f has growth rate \((-a)\) if \(f=g^{-1}\), where g has growth rate \(a\) #Function f has growth rate \((a+b)\) if \(f=g\circ h\), where g has growth rate \(a\) and h has growth rate \(b\) #Function f has growth rate \((a\alpha)\) if ##\(f\approx h_\alpha\) ##\(h_0(n)=n\) ##\(h_{\beta+1}(n)=h_\beta(g(n))\) ##\(h_\beta(n)=h_{\betan}(n)\) for limit ordinal \(\beta\) ##g has growth rate \(a\) #Function f has growth rate \((a/\alpha)\) if ##\(g\approx h_\alpha\) ##\(h_0(n)=n\) ##\(h_{\beta+1}(n)=h_\beta(f(n))\) ##\(h_\beta(n)=h_{\betan}(n)\) for limit ordinal \(\beta\) ##g has growth rate \(a\) Approximately, the "division by ordinal" eliminates the rightmost ordinal factor of a growth rate expression. Growth rate expressions have these properties: #The properties of addition and subtraction #\(((a\alpha)\beta)=(a(\alpha\beta))\) (so we can omit the brackets among multiplication) #\(((a/\alpha)/\beta)=(a/(\beta\alpha))\) #\(((a\alpha)/\alpha)=a\) #\((a/\alpha)\alpha=a\) #\(a(\alpha+\beta)=a\alpha+a\beta\) This notation can express more than using FGH scale as normal "growth rate", such as \((\varepsilon_0/(\omega^\omega+\omega^2))\) and \(((\omega^\omega+(-\omega^2))/\omega)\). The function in the previous blog thus has growth rate \((\varepsilon_0/\omega)\) (in HH scale). Growth rate (HH) multiplication and division Now growth rate expressions can multiply themselves, but with some restrictions since we have not found an inverse of growth rate multiplication. An addition-minus expression is built by the following rules: #An ordinal \(\alpha\) is an addition-minus expression #If \(a\) is an addition-minus expression, then \((-a)\) is an addition-minus expression #If \(a\) and \(b\) are addition-minus expressions, then \((a+b)\) is an addition-minus expression A growth rate expression is built by the following rules: #An addition-minus expression \(a\) is a growth rate expression #If \(A\) is a growth rate expression, \(a\) is an addition-minus expression, then \((Aa)\) is a growth rate expression #If \(A\) is a growth rate expression, \(a\) is an addition-minus expression, then \((A/a)\) is a growth rate expression Growth rates work as follows: #Function f has growth rate \(a\) if \(f\approx H_a\) for addition-minus expression \(a\) #Function f has growth rate \((Aa)\) if ##\(f\approx h_a\) ##\(h_0(n)=n\) ##\(h_{\alpha+1}(n)=h_\alpha(g(n))\) ##\(h_\alpha(n)=h_{\alphan}(n)\) for limit ordinal \(\alpha\) ##\(h_{(-b)}(n)=h_b^{-1}(n)\) ##\(h_{b+c}(n)=h_b(h_c(n))\) ##g has growth rate \(A\) #Function f has growth rate \((A/a)\) if ##\(g\approx h_a\) ##\(h_0(n)=n\) ##\(h_{\alpha+1}(n)=h_\alpha(f(n))\) ##\(h_\alpha(n)=h_{\alphan}(n)\) for limit ordinal \(\alpha\) ##\(h_{(-b)}(n)=h_b^{-1}(n)\) ##\(h_{b+c}(n)=h_b(h_c(n))\) ##g has growth rate \(A\) And \(abc\) is interpreted as \(((ab)c)\). General procedure of growth rate \(\alpha-1\) Functions with growth rate \(\alpha-1\) (in normal FGH scale, \(\alpha>0\)) can be built by the following procedure. If \(\alpha\) is successor, let \(\alpha=\beta+1\), then \(f_\beta\) with growth rate \(\beta\) is the same as \(\alpha-1\). If \(\alpha\) is limit, let \(m_\alpha(n)=\max\{m\in\mathbb N|f_\alpha(m)\le n\}\), \(F(n)=f_\alpha(m_\alpha(n)+1)\), then F has growth rate \(\alpha-1\), or \((\omega^\alpha/\omega)\) in HH scale. To directly build function with growth rate \((\alpha/\omega)\) (where \(\alpha\) is limit) in HH scale, let \(m_\alpha(n)=\max\{m\in\mathbb N|H_\alpha(m)\le n\}\), \(F(n)=H_\alpha(m_\alpha(n)+1)\), then F has this growth rate. However, those functions are hard to use "in reality", because they grow in a "jumping" way. The limit case is actually \[F(n)=\left\{ \begin{array}{ll} H_\alpha(1) & H_\alpha(0)\le n